package com.wc.blue_bridge_test.base.T4;

import java.util.Scanner;

/**
 * @Author congege
 * @Description Fibonacci数列
 * 矩阵快速幂
 * https://lx.lanqiao.cn/problem.page?gpid=T4
 * @Date Created in 2023/12/24-12:17
 */
public class Main {
    static int mod = 10007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] matrix = quickMin(n - 2);
        System.out.println(matrix[0][1]);
    }

    public static int[][] quickMin(int n) {
        int[][] origin = new int[][]{{1, 1}, {0, 0}};
        int[][] mulMatrix = new int[][]{{0, 1}, {1, 1}};
        int[][] ans = new int[][]{{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ans = mul(ans, mulMatrix);
            }
            mulMatrix = mul(mulMatrix, mulMatrix);
            n >>= 1;
        }
        return mul(origin, ans);
    }

    public static int[][] mul(int[][] matrix1, int[][] matrix2) {
        int[][] newMatrix = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    newMatrix[i][j] = (newMatrix[i][j] + matrix1[i][k] * matrix2[k][j]) % mod;
                }
            }
        }
        return newMatrix;
    }

}
